// https://leetcode.cn/problems/sqrtx/

#include <iostream>


using namespace std;
class Solution {
public:
    int mySqrt(int x) {
		if(x == 1) return 1;
		int left = 0, right = x;
		long long mid;
		while(left < right){
			if(right - left <= 1){
				return left;
			}
			mid = (left + right) / 2;
			cout << mid << " " << left << " " << right << endl;
			long long tmp = mid * mid;
			if(tmp == (long long)x ){
				return mid;
			}else if(tmp > x){
				right = mid;
			}else{
				left = mid;
			}
		}
		return mid;
    }
	
};

int main(){
	Solution so;
	int a = so.mySqrt(0);
	cout << a << endl;
	return 0;
}
